/**
 * 
 */
package string;

import utils.CreateUtils;

/**
 * @author Michael
 * Given two binary strings, return their sum (also a binary string)
 * e.g. "110"+"11"="1001"
 */
public class AddTwoBinaryStrings {

	public static String addIteration(String a, String b) {
		if (a == null)
			return b;
		if (b == null)
			return a;
		
		int carry = 0;
		int posA = a.length() - 1;
		int posB = b.length() - 1;
		StringBuilder sb = new StringBuilder(posA > posB ? posA + 1 : posB + 1);
		
		while (posA >= 0 && posB >= 0) {
			int sum = (a.charAt(posA) - '0') ^ (b.charAt(posB) - '0') ^ carry;
			sb.append(sum);
			carry = ( (a.charAt(posA) - '0') & (b.charAt(posB)) ) |
					( (a.charAt(posA) - '0') & carry )            |
					( (b.charAt(posB) - '0') & carry );
			--posA; --posB;
		}
		
		int pos = posA > posB ? posA : posB;
		String str = posA > posB ? a : b;
		while (pos >= 0) {
			int sum = (str.charAt(pos) - '0') ^ carry;
			sb.append(sum);
			carry = (str.charAt(pos) - '0') & carry;
			--pos;
		}
		if (carry > 0) { sb.append(carry); }
		
		return sb.reverse().toString();
	}
	
	
	public static String addIteration1(String a, String b) {
		if (a == null)
			return b;
		if (b == null)
			return a;
		
		int carry = 0;
		int sum = 0;
		int posA = a.length() - 1;
		int posB = b.length() - 1;
		StringBuilder sb = new StringBuilder();
		while (posA >= 0 && posB >= 0) {
			int add1 = a.charAt(posA) - '0';
			int add2 = b.charAt(posB) - '0';
			int total = add1 + add2 + carry;
			sum = total & 1;
			sb.append(sum);
			carry = total >> 1;
			posA--; posB--;
		}
		
		int pos = posA >= 0 ? posA : posB;
		String str = posA >= 0 ? a : b;
		for (; pos >= 0; --pos) {
			int add = str.charAt(pos) - '0';
			sum = add ^ carry;
			sb.append(sum);
			carry = add & carry; 
		}
		
		if (carry == 1)
			sb.append(carry);
		
		return sb.reverse().toString();
	}
	
	/**
	 * 
	 */
	public AddTwoBinaryStrings() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] numbers = { "11", "1", "0", "1111", "10000", "10010" };
		for (int i = 0; i < 10; i++) {
			String num1 = numbers[CreateUtils.randNonNegInt(numbers.length)];
			String num2 = numbers[CreateUtils.randNonNegInt(numbers.length)];
			System.out.println(num1 + " + " + num2 + " = " + addIteration(num1, num2));
		}

	}

}
